Sıralama algoritmasını adım adım keşfedin
Insertion Sort (Eklemeli Sıralama), bir kart oyuncusunun elindeki kartları sıralamasına benzer şekilde çalışan basit bir sıralama algoritmasıdır. Algoritma, diziyi sıralanmış ve sıralanmamış bölümlere ayırır. Her adımda, sıralanmamış bölümden bir eleman alınır ve sıralanmış bölümde doğru konumuna yerleştirilir.
1. Dizinin ilk elemanını zaten sıralanmış kabul ederiz.
2. Dizinin ikinci elemanından başlayarak her elemanı ele alırız.
3. Ele aldığımız elemanı, sıralanmış kısımdaki doğru yerine yerleştirmek için sıralanmış kısımdaki her elemanı sağa kaydırırız.
4. Bu işlemi dizinin sonuna kadar tekrarlarız.
Insertion Sort kararlı bir sıralama algoritmasıdır. Kararlılık, aynı değere sahip elemanların, sıralama sonrasında da ilk sıradaki göreceli konumlarını koruması anlamına gelir. Örneğin, aynı nota sahip iki öğrenci varsa ve ilk öğrenci listenin başında yer alıyorsa, sıralama sonrasında da ilk öğrenci diğerinden önce gelmeli.
Insertion Sort'ta kararlılık, elemanları yalnızca kendilerinden daha büyük elemanların önüne yerleştirdiğimiz için ve eşit değerli elemanların sırasını değiştirmediğimiz için sağlanır.
| Durum | Zaman Karmaşıklığı | Açıklama |
|---|---|---|
| En İyi Durum | O(n) | Dizi zaten sıralıysa, her eleman için sadece bir karşılaştırma yapılır. |
| Ortalama Durum | O(n²) | Her eleman için ortalama n/2 karşılaştırma yapılır. |
| En Kötü Durum | O(n²) | Dizi ters sıralıysa, her eleman için yaklaşık n karşılaştırma yapılır. |
| Uzay Karmaşıklığı | O(1) | Algoritma, sabit miktarda ekstra bellek kullanır (yerinde/in-place sıralama). |
Insertion Sort aşağıdaki durumlarda tercih edilir:
Insertion Sort, küçük dizilerde oldukça etkilidir ve büyük sıralama algoritmaları (Quicksort, Mergesort) içinde alt-rutin olarak kullanılabilir. Ayrıca, gelen verileri anında sıralı bir yapıya eklemek gerektiğinde de kullanışlıdır.
Insertion Sort'un mantığını günlük hayatta da görürüz: